There are known processors having branch instructions for determining branch target address values by calculating the sum of a register value in the processor and a constant value (referred to as an “immediate value”) included in an instruction word at an execution time. In particular, when the register is the program counter (PC), which indicates the address of the instruction currently being executed (i.e. program counter (PC) address), the target location is relative to the location of the branch instruction. This type of branch instruction is employed in many processors because it enables branches to jump a fixed location in the program regardless of the address placement of the program. In this case, the immediate value in the instruction word of the branch instruction is referred to as a displacement (abbreviated “disp”), and the branch instruction is called a program counter (PC) relative branch instruction with displacement (abbreviated as a “PC+disp branch instruction” below). One example of this type of branch instruction is the BRA instruction described on pages 10 to 22 of “The SH7750 Programming Manual” published by Hitachi Ltd. in 1998.
A PC+disp branch instruction is executed in a two-step operation: (1) determining the branch target address, in many cases by performing a sign extension of the disp to align it with the bit-width of the program counter and then calculating the sum of the value of the PC and the sign-extended disp; and (2) fetching an instruction by using the branch target address. The sign extension refers to a process of converting a signed binary integer with a width of m bits to a signed binary integer with a width of n (>m) bits, which can be implemented by copying the source integer to the lower m bits of the target integer, and copying the most significant bit of the source integer, or sign bit, to each of the upper n-m bits of the target integer. An example of the address calculation (1) above will now be shown in FIG. 1.
Reference numeral 111 indicates the 32-bit address of the instruction being executed, i.e., the value of the PC. Reference numeral 112 indicates the instruction word of a PC+disp branch instruction with the lower 12 bits representing the disp. The format of the instruction word 112 is shown in FIG. 2. Reference numeral 201 indicates the instruction op code. The instruction op code for a PC+disp branch instruction is 4 bits long. Reference numerals 202 and 203 indicate portions of the disp, namely, the highest 1 bit and lower 11 bits within the displacement, respectively. Reference numeral 204 indicates the 12-bit signed disp, consisting of the highest 1 bit 202 and the lower 11 bits 203. That is, the highest 1 bit 202 of the disp is the sign bit of the disp.
The branch target address 114 is obtained in a 32-bit adder 121 by calculating the sum of the address 111 and a value 113 obtained by sign-extending the disp value 204 in the instruction word 112 to 32 bits.
A PC+disp branch instruction intrinsically requires an n-bit addition operation for calculating the branch target address. An n-bit addition operation requires time of the order of logn, and this addition operation time has been considered to be inevitable in prior processors.
According to the description on pages 12 to 15 and 22 of “MICROPROCESSOR REPORT” published on Sep. 13, 1999, ‘Sun Micro Systems’, MAJC architecture has adopted a semi-absolute branch (abbreviated as “SemiABS branch” below) instruction rather than a PC+disp branch instruction to reduce the addition operation time mentioned above. A SemiABS branch instruction specifies some of address bits as an absolute address. FIG. 3 shows the address calculation method of a SemiABS branch instruction.
Reference numeral 311 indicates the PC value as in the case of a PC+disp branch instruction. Reference numeral 312 indicates the instruction word of a SemiABS branch instruction. FIG. 4 shows the instruction format of a SemiABS branch instruction. Reference numeral 401 indicates an operand field which is additional to the operand fields for the instruction op code and branch target address calculation. Reference numerals 402 and 403 indicate operand fields used for branch target address calculation. The lower 12-bit portion in the instruction word 312 represents operand 403, and the next upper 2-bit portion represents operand 402.
In the calculation of the branch target address 314, the lowest 2 bits are set to “00” (a constant value), and the next 12-bit to the lowest 2 bits portion accommodates operand portion 403 in the instruction word 312 is set as is. For the next 18-bit portion, the sum of the 18-bit sign-extended value 313 of operand portion 402 in the instruction word 312 and the PC value 311 is calculated in an 18-bit adder 321 and outputted.
A SemiABS branch requires an adder with fewer digits for branch target address calculation than in the case of a PC+disp branch, so the delay time can be reduced accordingly, and higher operating frequencies can be expected.
Especially in a processor having an instruction cache, a SemiABS branch allows faster processing. The execution of a branch instruction requires access to the instruction cache after the branch target address calculation, and ordinary cache operations are performed in two steps: (1) inputting the index portion of an address to the cache array and reading a corresponding tag portion and data from it, and (2) comparing the tag portion output in (1) with a portion of the address corresponding to the tag portion, and outputting the data as a cache hit if these portions match. That is, input of the index portion to the cache has to precede the timing of the input of the tag portion. In addition, the index portion of an address is usually placed in the lower portion of the address.
A SemiABS branch outputs the lower portion of the branch target address as is without performing addition. When the bit range of the index portion is included in the bit range that is not submitted to the addition operation, access to the cache array can start without waiting for the completion of the calculation of the upper portion of the branch target address. This speeds up the execution of the branch instruction as a whole.
The prior art described above has introduced a new SemiABS branch to implement a fast branch in place of the PC+disp branch. However, a new processor adopting the SemiABS branch logic system cannot execute programs written with non-SemiABS branch instructions. That is, object code that runs on a processor having existing PC+disp branch instructions contains no SemiABS branch instructions which accordingly cannot benefit from the faster performance.
In addition, a SemiABS branch makes it necessary to specify portion of a branch target address as an absolute address, which makes it impossible to determine whether the address is within the range of the branch target address at compile time, and that compiled object code is not relocatable. The term “relocatable” refers to a state in which object code is executable regardless of its address location.